// 题目要求：
// 给一个长度为 n 的数组，里面是 1 ~ n 的数字排列
// 在只能入栈和出栈的操作中，能输出的最大字典序的排列是多少

// 解题思路：
// 核心思路：要考虑栈顶的元素和栈外剩余的元素中的最大值哪个大
// 如果栈顶元素比较大，那就要出栈
// 如果剩余的元素最大值更大，那就将这个最大值前面（包括这个元素）入栈，再出栈

import java.util.Stack;

public class StackAndSort {
    // 解法 1：
    public int[] solve1 (int[] a) {
        int n = a.length;

        int[] b = new int[n];
        b[n - 1] = a[n - 1];
        for(int i = n - 2; i >= 0; i--){
            b[i] = Math.max(b[i + 1], a[i]);
        }

        Stack<Integer> stack = new Stack<>();

        int[] ret = new int[n];
        int pos = 0;
        int j = 1;
        for(int i = 0; i < n; i++){
            stack.push(a[i]);
            boolean flag = false;
            while(!stack.isEmpty() && j < n && stack.peek() >= b[j]){
                int t = stack.pop();
                ret[pos] = t;
                pos++;
            }
            j++;
        }

        while(!stack.isEmpty()){
            int t = stack.pop();
            ret[pos] = t;
            pos++;
        }

        return ret;
    }

    // 解法 2：
    public int[] solve2 (int[] a) {
        int n = a.length;

        Stack<Integer> stack = new Stack<>();
        boolean[] hash = new boolean[n + 1];
        int aim = n;

        int[] ret = new int[n];
        int pos = 0;
        int i = 0;
        while(i < n){
            while(!hash[aim]){
                stack.push(a[i]);
                hash[a[i]] = true;
                i++;
            }
            while(hash[aim]){
                aim--;
            }
            while(!stack.isEmpty() && stack.peek() > aim){
                int t = stack.pop();
                ret[pos++] = t;
                hash[t] = false;
            }
        }

        return ret;
    }
}
